package main

func main() {
	println("二叉树查找")
}

type Node struct {
	value int   // 节点存储的值
	left  *Node // 左子节点指针
	right *Node // 右子节点指针
}

// 插入新元素
func (n *Node) Insert(value int) *Node {
	if n == nil { // 当前节点为空，创建一个新节点并返回
		return &Node{value: value}
	}
	if value < n.value { // 插入左子树
		n.left = n.left.Insert(value)
	} else if value > n.value { // 插入右子树
		n.right = n.right.Insert(value)
	}
	println("插入新元素成功")
	return n
}

// 查找元素是否存在
func (n *Node) Search(value int) bool {
	if n == nil { // 根节点为空，直接返回 false
		return false
	}
	if value == n.value { // 找到了目标元素
		return true
	} else if value < n.value { // 在左子树中查找
		return n.left.Search(value)
	} else { // 在右子树中查找
		return n.right.Search(value)
	}
}

// 删除指定元素
func (n *Node) Delete(value int) *Node {
	if n == nil { // 根节点为空，直接返回
		return nil
	}
	if value < n.value { // 在左子树中删除目标元素
		n.left = n.left.Delete(value)
		return n
	} else if value > n.value { // 在右子树中删除目标元素
		n.right = n.right.Delete(value)
		return n
	} else { // 找到了目标元素
		if n.left == nil && n.right == nil { // 情况1：没有子节点，直接删除
			return nil
		} else if n.left == nil || n.right == nil { // 情况2：只有一个子节点，用该子节点替换当前节点即可
			var child *Node
			if n.left != nil {
				child = n.left
			} else {
				child = n.right
			}
			return child
		} else { // 情况3：有两个子节点，找到右子树的最小值来替换当前节点，并在右子树中递归删除该最小值节点。
			min := findMin(n.right)
			minCopy := &Node{value: min}
			right := deleteMin(n.right)
			minCopy.left, minCopy.right = n.left, right
			return minCopy
		}
	}
	return nil
}

// 查找右子树的最小值（用于删除情况3）
func findMin(n *Node) int {
	for n.left != nil {
		n = n.left
	}
	return n.value
}

// 删除右子树的最小值（用于删除情况3）
func deleteMin(n *Node) *Node {
	if n.left == nil {
		return n.right
	}
	n.left = deleteMin(n.left)
	return n
}
